不動点コンビネータを javascript で作る
不動点コンビネータってのは関数を再帰してくれるすごいやつだよ
ここ読んでやった↓
大体これ読めば良いけど一応自分で咀嚼して自分なりに再整理してみた
使用言語が javascript なのは無名関数が使えて、関数呼び出しが簡素で、今ここを見ている人がブラウザですぐにお試しできるから
さあ君もF12キーを押して試してみよう（詳しい使い方は各ブラウザで調べて）
0. 前提
分かりやすい再帰関数の例としてとりあえず階乗を使う
最初の状態はこう
code:js
var fact = (n) => { return n == 0 ? 1 : n * fact(n-1); };
fact(5); // => 120
こんな感じの関数を無名関数のみで作りたい
今は関数の中でfactという関数名を使ってしまっているので無名関数とは言えない
1. 関数名で呼び出すのをやめる
まず関数内でfact自身を呼び出すことを辞めよう
最初のfactと区別して_factとする
code:js
var _fact = (n) => { return n == 0 ? 1 : n * f(n-1); };
_fact(5); // => エラー
当然「fなんてねーぞ」と怒られるので、fは引数でどうにかして自分自身を渡すようにしよう
code:js
var _fact = (f, n) => { return n == 0 ? 1 : n * f(n-1); };
_fact(_fact, 5); // => エラー
今度は引数の数があってないので怒られる
code:js
var _fact = (f, n) => { return n == 0 ? 1 : n * f(f, n-1); };
_fact(_fact, 5); // => 120
パッと見「_factが2回出てきてるし何も進展していないのでは？」と思われるかもしれない
_fact内から_factを参照しているわけではないので無名関数化には成功している
実際コピペすればこんな風に関数名を一切使わずに式を書くことができる
code:js
((f, n) => {
return n == 0 ? 1 : n * f(f, n-1);
})((f, n) => {
return n == 0 ? 1 : n * f(f, n-1);
}, 5); // => 120
無名関数化は達成されたが、このままでは再帰関数を必要とする度に同じ関数を2回書くという馬鹿げたことをせねばならない
というかf(f, n-1)という再帰の呼び出し方も何だか気持ち悪いのでf(n-1)に戻したい
2. カリー化
カリー化ってのは関数の引数を全部1つにすること
複数の引数を取る関数は1つの引数を取る関数を入れ子にして再現する
そうすると「部分的に代入された状態の式」を扱ったり出来て何かと便利なのだ
具体的に何をするのかは以下のプログラムを見た方が早い
code:js
var _fact = (f) => { return (n) => { return n == 0 ? 1 : n * f(f)(n-1); }; };
_fact(_fact)(5) // => 120
これを見てると2つの事が思い浮かぶ
_factの内側の関数が元のfactに酷似している
もしかしてfactからいい感じに_factみたいなのを生成する関数作れるのでは？
_fact(_fact)も「関数を2回繰り返す」という関数を作れば同じことを2回書かなくて良くなるのでは？
これらを順番に解決していく
3. 関数を再帰のために変形させる関数
2で作った_factのような関数をfactから作る関数を作る
カリー化と関数を引数に取るところだけは無名関数化のために必要なことなのでそれだけfactに適用した
話を先取りすると最終的に作りたい関数が「Zコンビネータ」という名前で、Zコンビネータの一部だからひとまず_Zという名前の関数にする
code:js
var fact = (f) => { return (n) => { return n == 0 ? 1 : n * f(n-1); }; };
var _Z = (f) => { return (g) => { return f(g(g)); }; };
var _fact = _Z(fact)
_fact(_fact)(5) // => エラー
とりあえず安易な発想でやるとこうなる
fに代入されるのはfactで、gに代入されるのは_fact
つまり_factはfactに「入れ子にした_fact」を食わせたもの
エラーになるのは何故かと言うとこんな感じで式の展開が無限ループするから
code:js
_fact(_fact)
_Z(fact)(_fact)
( (g) => { return fact(g(g)); } )(_fact)
fact(_fact(_fact))//factが1個増えた
fact(_Z(fact)(_fact))
fact(( (g) => { return fact(g(g)); } )(_fact))
fact(fact(_fact(_fact)))//fact2個目
//以下エンドレス
呼び出されるまで展開されないようにする
code:js
var fact = (f) => { return (n) => { return n == 0 ? 1 : n * f(n-1); }; };
var _Z = (f) => { return (g) => { return (x) => { return f(g(g))(x); }; }; };
var _fact = _Z(fact)
_fact(_fact)(5) // => 120
代入する処理まで関数に丸め込んだので、実際に値を代入するまで関数は展開されない
実際の代入は有限回しか行われないので無限ループにはならない
所謂「純粋関数型言語」と呼ばれる言語では大抵の場合「呼び出すまで展開しない」という「遅延評価」と呼ばれるルールがあるのでこの問題は発生しない
4. 2度繰り返す
_factや_Zは説明上あると便利なので用意しただけで最終的には取り去りたい
つまり_fact = _Z(fact)や_fact(_fact)みたいな処理を全部1つの関数にまとめる
code:js
var fact = (f) => { return (n) => { return n == 0 ? 1 : n * f(n-1); }; };
var _Z = (f) => { return (g) => { return (x) => { return f(g(g))(x); }; }; };
var Z = (f) => { return _Z(f)(_Z(f)); };
Z(fact)(5) // => 120
factと_Zの定義は3.と同じ
関数食わせるといい感じに関数を再帰させてくれるこのZって関数を不動点コンビネータと呼ぶ
特にこの形の式にはZコンビネータって名前がついてるらしい
Z以外にもYとかチューリングとか色々あるそう
実装の仕方、関数の構造が違うだけでやることは同じ
読みやすさを優先して_Zを入れているが、実際には_Zを挟む必要は無い
_Zを入れないとこう
code:js
var fact = (f) => { return (n) => { return n == 0 ? 1 : n * f(n-1); }; };
var Z = (f) => {
return ( (g) => { return (h) => { return (x) => { return g(h(h))(x); }; }; }
)(f)( ((g) => { return (h) => { return (x) => { return g(h(h))(x); }; }; })(f) );
};
Z(fact)(5) // => 120
一切関数名を排除するとこう
code:js
((f) => {
return ( (g) => { return (h) => { return (x) => { return g(h(h))(x); }; }; }
)(f)( ((g) => { return (h) => { return (x) => { return g(h(h))(x); }; }; })(f) );
})(
(f) => { return (n) => { return n == 0 ? 1 : n * f(n-1); }; }
)(5) // => 120
こうして無名関数だけで再帰できることが証明された めでたしめでたし
5. まとめ
"無名"関数はその名の通り名前が無いのでそのまま再帰呼び出しはできない
ループするためには再帰をする必要があるが、無名関数なのでそのままでは難しい
まず、再帰させたい関数に自分自身が代入されることを想定した引数を加える
次に、その関数を不動点コンビネータに食わせる
あら不思議再帰関数の出来上がり